//给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
//字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

//示例 1:
//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
//示例 2:
//输入: strs = [""]
//输出: [[""]]
//示例 3:
//输入: strs = ["a"]
//输出: [["a"]]

//提示：
//1 <= strs.length <= 104
//0 <= strs[i].length <= 100
//strs[i] 仅包含小写字母

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<string> strs0 = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<string> strs1 = {"a"};

class Solution {
public:
    // since the length of strs is not large, the number of str permutations is large, a hash table with ordered
    //    rearrangement of str as the key is constructed
    // save the origin string directly, do not save index
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (auto & str:strs){
            string key = str;
            sort(key.begin(), key.end());
            map[key].emplace_back(str);
        }

        //输出结果
        vector<vector <string> > answer;
        for (const auto& item:map){
            answer.emplace_back(item.second);
        }
        return answer;
    }
};
int main() {
    Solution solution;
    auto ans = solution.groupAnagrams(strs1);
    for(auto vec:ans){
        for(auto item:vec){
            cout<<item<<" ";
        }
        cout<<endl;
    }

}
